package _0_3_打家劫舍

/*
原题链接:
https://leetcode.cn/problems/house-robber-iii/

337. 打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，
聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:
输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

思路:
一. 确定递归函数的参数和返回值
这里要求一个节点, 偷和不偷的两个状态所得的钱, 那么返回值就是一个长度为2的数组.
dp[i]: 下标为0记录不偷该节点所得到的最大金钱数, 下标为1记录偷该节点所得到的最大金钱数

所以本题dp数组就是一个长度为2的数组
可能会有疑问, 长度为2的数组怎么标记树种每个节点的状态呢?
别忘了在递归的过程中, 系统栈会保存每一层递归的参数

二. 确定终止条件
在遍历过程种, 如果遇到空节点的化, 很明显, 无论偷还是不偷都是0, 所以就返回
  - if cur == nil {
    return vector<int>{0,0}
    }

这也相当于dp数组的初始化

三. 确定遍历顺序
首先明确的是使用后序遍历. 一位内要通过递归函数的返回值来做下一步计算
通过递归左节点, 得到左节点偷与不偷的金钱
通过递归右节点, 得到右节点偷与不偷的金钱.
//下标0:不偷		下标1:偷
vector<int> left = robTree(cur->left) //左
vector<int> right = robTree(cur->right) //右
//种

四. 确定单层递归的逻辑
如果是偷当前节点, 那么左右孩子就不能偷,
  - val1 = cur.val + left[0] + right[0]
    val2 = max(left[0], left[1]) + max(right[0], right[1])
    return {val2, val1}
*/
func rob3(root *TreeNode) int {
	val := dfs(root) //获取dfs结果数组

	return max(val[0], val[1]) //返回较大值
}

func dfs(node *TreeNode) []int {
	if node == nil { //1.如果node为nil,直接返回[]int{0,0}即可
		return []int{0, 0}
	}

	left, right := dfs(node.Left), dfs(node.Right)                 //2.递归调用左节点和右节点
	selected := node.Val + left[1] + right[1]                      //3.声明如果选择当前节点,dp数组的情况
	notSelected := max(left[0], left[1]) + max(right[0], right[1]) //4.声明如果不选择当前节点, dp数组的情况

	return []int{selected, notSelected} //5.返回选择和不选择的结果数组
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
